#pragma once
#include "Queue.h"
#include "Stack.h"


template <class TYPE>
struct Vertex;
template <class TYPE>
struct Arc;

template <class TYPE>
struct Vertex{
	Vertex<TYPE>	*pNextVertex;
	TYPE			data;
	int				inDegree;
	int				outDegree;
	short			processed;
	Arc<TYPE>		*pArc;
};

template <class TYPE>
struct Arc{
	Vertex<TYPE> *destination;
	Arc<TYPE> *pNextArc;
};

template <class TYPE, class KTYPE>
class Graphs
{
private:
	int count;
	Vertex<TYPE> *first;
public:
	Graphs(void);
	~Graphs(void);
	
	int insertVertex	(TYPE dataIn);
	int deleteVertex	(KTYPE delKey);
	int insertArc		(KTYPE keyFrom, KTYPE keyTo);
	int deleteArc		(KTYPE keyFrom, KTYPE keyTo);
	int retrieveVertex	(KTYPE key,		TYPE& dataOut);
	int firstArc		(KTYPE key,		TYPE& dataOut);
	bool EmptyGraph		(void);
	bool graphFull		(void);
	int graphCount		(void);
	void depthFirst		(void (*process)(TYPE dataProc));
	void breadthFirst	(void (*process)(TYPE dataProc));
};

template <class TYPE, class KTYPE>
Graphs<TYPE>::Graphs() {
	first = nullptr;
	count = 0;
}

template <class TYPE, class KTYPE>
int Graphs<TYPE, KTYPE>::insertVertex(TYPE dataIn) {
	Vertex<TYPE> *newPtr = new Vertex<TYPE>;
	if(!newPtr) return = -1;
	else {
		newPtr->data = dataIn;
		newPtr->inDegree = 0;
		newPtr->outDegree = 0;
		newPtr->pArc = nullptr;
		newPtr->pNextVertex = nullptr;
		newPtr->processed = 0;
		success = 1;
		count++;
		return 1;
	}

	Vertex<TYPE> *pLoc = first;
	if(!pLoc) {
		first = newPtr;
	}
	else {
		Vertex<TYPE> *pPreLoc = first;
		while(pLoc && dataIn.key > (pLoc->data).key){
			pPreLoc = pLoc;
			pLoc = pLoc->pNextVertex;
		}
		if(pPreLoc == first){
			newPtr->pNextVertex = first;
			first = newPtr;
		}
		else {
			pPreLoc->pNextVertex = newPtr;
			newPtr->pNextVertex = pLoc;
		}
	}
	return 1;
}

template <class TYPE, class KTYPE>
int Graphs<TYPE, KTYPE>::deleteVertex(KTYPE delKey) {
	Vertex<TYPE> *pPre;
	Vertex<TYPE> *pTemp;
	if(!first) return -2; //
	pPre = nullptr;
	pTemp = first;
	// each vertex is identified by its key value
	while(pTemp && (pTemp->data).key < delKey) {
		pPre = pTemp;
		pTemp = pTemp->pNextVertex;
	}

	// if key not found
	if(!pTemp || delKey != (pTemp->data.key))
		return -2;

	// if degree is not zero
	if(pTemp->inDegree > 0 || pTemp->outDegree > 0)
		return -1;
	if(!pPre)
		first = pTemp->pNextVertex;
	else
	{
		pPre->pNextVertex = pTemp->pNextVertex;
		delete pTemp;
	}
	count--;
	return 1; // success
}
	
template <class TYPE, class KTYPE>
Graphs<TYPE, KTYPE>::insertArc(KTYPE keyFrom, KTYPE keyTo) {
	Arc<TYPE> *pArcNew = nullptr;
	Vertex<TYPE> *pVerFrom = nullptr;
	Vertex<TYPE> *pVerTo = nullptr;

	if(!(pArcNew = new Arc<TYPE>)) return -1; // memory overflow

	// Locate the source vertex
	pVerFrom = first;
	while(!pVerFrom && pVerFrom->data.key < keyFrom) {
		pVerFrom = pVerFrom->pNextVertex;
	}
	if (!pVerFrom) return -2; // Key of From not found

	// Locate the To Vertex
	pVerTo = first;
	while(!pVerTo && pVerTo->data.key < keyTo) {
		pVerTo = pVerTo->pNextVertex;
	}
	if (!pVerTo) return -3; // Key of To not found

	// from and to vetices are located. Insert new arc
	pVerFrom->outDegree++;
	pVerTo->inDegree++;
	pArcNew->destination = pVerTo;
	// pArc = null, insert to first arc
	if(!(pVerFrom->pArc)) { 
		pVerFrom->pArc = pArcNew;
		pArcNew->pNextArc = nullptr;
		return 1; // success
	}

	// Find insert point in adjacency arc list
	Arc<TYPE> *pArcPre = nullptr;
	Arc<TYPE> *pArcTemp = pVerFrom->pArc;
	while (pArcTemp && keyTo >= pArcTemp->destination->data.key)
	{
		pArcPre = pArcTemp;
		pArcTemp = pArcTemp->pNextArc;
	}
	// pArcPre = null, insert before first arc
	if(!pArcPre) { 
		pVerFrom->pArc = pArcNew;
	}
	else {
		pArcPre->pNextArc = pArcTemp;
	}
	pArcNew->pNextArc = pArcTemp;
	return 1; // success
}















